首页 > 试题广场 >

反转链表

[编程题]反转链表

热度指数：1762281 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围： $0\leq n\leq1000$

要求：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$ 。

如当输入链表{1,2,3}时，

经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。

以上转换过程如下图所示：

示例1

输入

{1,2,3}

输出

{3,2,1}

示例2

输入

{}

输出

{}

说明

空链表则输出空

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

算法知识视频讲解

推荐

writezen

public class Solution {
 public static ListNode ReverseList(ListNode head) {
 if(head==null)
 return null;
 ListNode reversedHead=null;
 ListNode current=head;
 ListNode tmp=null;
 ListNode pre=null;
 while(current!=null){
 tmp=current.next;
 current.next=pre;
 if(tmp==null)
 reversedHead=current;
            pre=current;
 current=tmp;
 
 }
 return reversedHead;
 }
}

编辑于 2015-06-19 16:46:40 回复(64)

Python 3

wawaha

def teat(*args):

x = args

if len(x) == 0:

return {}

else:

t = list(x)

t.reverse()

return t

c = teat()

发表于 2023-02-06 10:12:26 回复(0)

Python 3

牛客离谱号

反转链表，尾插法

class Solution:
    def ReverseList(self , head: ListNode) -> ListNode:
        # write code here
        tail = head
        if(tail != None):
            while(tail.next != None):#寻找尾结点
                tail = tail.next
            while(head != tail ):
                point2 = head
                head = head.next
                point2.next = tail.next
                tail.next = point2
        return tail

三个指针分别指向头结点（head）、尾结点（tail）和待移动节点（point2）。

每次移动将head插入tail之后point2之前

发表于 2022-09-13 18:09:45 回复(0)

Python 3

准备回家种田的程序猿

# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param head ListNode类
# @return ListNode类
#
class Solution:
__slots__=()
def ReverseList(self , head: ListNode) -> ListNode:
if not head:return head
# write code here
node_li=[] #遍历一遍链表，将所有节点添加到一个列表中
while head:
node_li.append(head)
head=head.next

new_head=node_li.pop()
tmp_new_head=new_head #真正的头结点

#从后向前重新构建链表
while node_li:
cur_node=node_li.pop()
cur_node.next=None
new_head.next=cur_node
new_head=new_head.next

return tmp_new_head

发表于 2022-08-14 17:17:07 回复(0)

Python 3

来牛客玩玩

class Solution:
    def ReverseList(self , head: ListNode) -> ListNode:
        # write code here
        if not head&nbs***bsp;not head.next:
            return head
        p1, p2 = head, None
        while p1:
            temp = p1.next
            p1.next = p2
            p2 = p1
            p1 = temp
        return p2

发表于 2022-07-26 11:49:44 回复(0)

Python 3

lun__

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @return ListNode类
#

class Solution:
    def ReverseList(self , head: ListNode) -> ListNode:
        ## 直接反转  
        cur = head 
        pre = None  
        while (cur != None): 
            temp = cur.next  ## 保存cur.next之后的内容 
            cur.next = pre   ## 完成反转指向 
            
            pre = cur        ## 交换 pre和cur 
            cur = temp 
        return pre  
    
        

class Solution:
    def ReverseList(self , head: ListNode) -> ListNode:
        ## 链表 ———> 数组 ————> 反转数组 ————> 链表
        ### 由链表生成数组 
        dummy = ListNode(-1) 
        dummy.next = head 
        cur = dummy
        alist = [] 
        while (cur.next != None): 
            cur = cur.next 
            alist.append(cur.val) 
            
        alist.reverse() ## 翻转 
        
        ## 由数组生成链表 
        dummy = ListNode(-1) 
        dummy.next = head 
        cur = dummy
        for i in range(len(alist)): 
            cur.next = ListNode(alist[i]) 
            cur = cur.next 
        return dummy.next

发表于 2022-07-16 16:01:47 回复(1)

Python 3

风软一江山

class Solution:
    def ReverseList(self , head: ListNode) -> ListNode:
        curr = None
        while head:
            temp = head.next
            head.next = curr
            curr = head
            head = temp
        return curr

发表于 2022-07-07 23:56:15 回复(0)

Python 3

Vivimore

class Solution:
    def ReverseList(self , head: ListNode) -> ListNode:
        pre = None
        cur = head
        while cur:
            next_node = cur.next
            cur.next = pre
            pre = cur
            cur = next_node
        return pre

发表于 2022-06-16 09:47:01 回复(0)

Python 3

一万个小仙女

简单

s = input()
s1 = s[1:-1]
if s1 == "":
print('{}')
else:
s2 = s1.split(',')
s2.reverse()
s3 = ",".join(s2)
print('{'+s3+'}')

发表于 2022-06-08 21:57:33 回复(0)

Python 3

yifan1997

class Solution:
    def ReverseList(self , head: ListNode) -> ListNode:
        # write code here
        pre=None
        cur=head
        while(cur!=None):
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        return pre

发表于 2022-05-19 18:19:03 回复(0)

Python 3

牛客531845871号

为什么python3的代码在leetcode中递归可以通过这里就不行 [1, ...., 1000]的链表？

发表于 2022-05-13 11:10:29 回复(0)

Python 3

godylf

class Solution:
    def ReverseList(self , head: ListNode) -> ListNode:
        # write code here
        if head==None:
            return None
        elif head.next==None:
            return head
        else:
            head_next=head.next
            head_next_two=head.next.next
            head.next=None #容易忽略了的
            while head_next_two:
                head_next.next=head
                head=head_next
                head_next=head_next_two
                head_next_two=head_next_two.next
            head_next.next=head
            return head_next

发表于 2022-04-26 23:45:47 回复(0)

Python 3

牛客190658020号

思路就是遍历一个出来只想新链表的头就好了

发表于 2022-04-13 12:43:14 回复(0)

Python 3

我是赵同学

前向迭代就是每次通过一个变量记录当前位置的下一位置，然后将此位置指向反转列表的位置头部，让它设置成为新的头部，并且让当前位置变为下一位置。

递归就是依次将下一个位置传递给这个反转列表的函数中，然后直到最后一位置的时候将它返回，这样就有了一个变量来记录了最后一个位置。然后开始反向迭代，反向迭代过程中依次将对应的位置的下一位置(head.next)指向自己(head.next.next=head)，然后将自己指向空。

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @return ListNode类
#
class Solution:
    def ReverseList(self , head: ListNode) -> ListNode:
        # write code here
#迭代   
        if head == None:
            return head
        rev = None
        while head:
            tmp = head.next
            head.next = rev
            rev = head
            head = tmp 
        return rev

#递归
#         import sys
#         sys.setrecursionlimit(1000000)  #递归最多1000次左右,改变递归最大深度
#         if head == None&nbs***bsp;head.next == None:
#             return head
#         rev = self.ReverseList(head.next)
#         head.next.next = head
#         head.next = None
#         return rev

发表于 2022-04-03 20:15:33 回复(0)

Python 3

我叫不要脸

class Solution:
    def ReverseList(self , head: ListNode) -> ListNode:
        # write code here
        if not head&nbs***bsp;not head.next:
            return head
        reverl = self.ReverseList(head.next)
        head.next.next = head
        head.next = None
        return reverl

发表于 2022-03-20 14:48:47 回复(0)

Python 3

想起来就做两道（JihongRen）

class Solution:
    def ReverseList(self , head: ListNode) -> ListNode:
        rev_head = None
        while head is not None:
            curr = head
            head = head.next
            curr.next = rev_head
            rev_head = curr
        return rev_head

发表于 2022-03-11 23:13:11 回复(0)

Python 3

JaydenCheng

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @return ListNode类
#
class Solution:
    def ReverseList(self , head: ListNode) -> ListNode:
        if head == None:
            return None
        temp0 = None
        temp1 = head
        temp2 = head.next
        temp1.next = temp0
        while temp2 != None :
            temp0 = temp1
            temp1 = temp2
            temp2 = temp2.next
            temp1.next = temp0
        return temp1

发表于 2022-02-14 11:37:51 回复(0)

Python 3

苏堤

# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param head ListNode类
# @return ListNode类
#
class Solution:
def ReverseList(self , head: ListNode) -> ListNode:
if head is None or head.next is None:
return head
pre=None
cur=head
while(cur!=None):
next=cur.next
cur.next=pre
pre=cur
cur=next
return pre

发表于 2021-12-18 01:03:10 回复(0)

Python 3

Joy_9

class Solution:
    def ReverseList(self , head: ListNode) -> ListNode:
        if not head:
            return head
        
        node=head.next
        head.next=None
        
        while node:
            new=node.next
            node.next=head
            head=node
            node=new
        return head

发表于 2021-12-14 01:05:25 回复(0)

提交观点

问题信息

链表

来自：寻找时间黑客在线编程大...

难度：

37条回答 5903收藏 335851浏览

通过挑战的用户

查看代码

牛客11552...

2023-03-14 11:22:15
洞洞鞋小公子

2023-03-12 22:30:58
牛客20133...

2023-03-09 16:07:56
松林子木

2023-03-08 10:28:45
牛客17038...

2023-03-07 15:45:53

反转链表

输入

输出

输入

输出

说明

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

问题信息

热门推荐

通过挑战的用户

相关试题